`
https://leetcode.cn/problems/random-pick-with-weight/
`

/**
 * @param {number[]} w
 */
var Solution = function (w) {
  this.preSum = [0];
  for (let i = 0; i < w.length; i++) {
    this.preSum.push(this.preSum[this.preSum.length - 1] + w[i]);

  }
};

/**
* @return {number}
*/
Solution.prototype.pickIndex = function () {
  const n = this.preSum.length;
  // 生成在闭区间 [1, preSum[n - 1]] 中的随机整数
  const target = Math.floor(Math.random() * this.preSum[n - 1]) + 1;

  // 获取 target 在前缀和数组 preSum 中的索引
  // 别忘了前缀和数组 preSum 和原始数组 w 有一位索引偏移
  return left_bound(this.preSum, target) - 1;
};

// 搜索左侧边界的二分搜索
function left_bound(nums, target) {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return left;
};

/** 
* Your Solution object will be instantiated and called as such:
* var obj = new Solution(w)
* var param_1 = obj.pickIndex()
*/